/**
 * 
 */
package cz.cuni.mff.abacs.burglar.logics;

import aStarLibrary.Node;
import cz.cuni.mff.abacs.burglar.logics.objects.BaseInterface;
import cz.cuni.mff.abacs.burglar.logics.objects.BaseObject;
import cz.cuni.mff.abacs.burglar.logics.objects.Room;
import cz.cuni.mff.abacs.burglar.logics.objects.agents.Agent;
import cz.cuni.mff.abacs.burglar.logics.objects.agents.Burglar;
import cz.cuni.mff.abacs.burglar.logics.objects.agents.Guard;
import cz.cuni.mff.abacs.burglar.logics.objects.items.Item;
import cz.cuni.mff.abacs.burglar.logics.objects.positions.*;
import java.util.*;


/**
 * The basic map/level representation structure, holds lists of different
 * types of objects and provides search functionality on them.
 * 
 * @author abacs
 *
 */
public abstract class DataMap implements GameMap {
	
	
	/** The next unused id. */
	private int _nextID;
	
	/** Number of horizontal game map positions. */
	private int _width = 0;
	/** Number of horizontal game map positions. */
	private int _height = 0;
	
	
	/** List of all agents in the map. */
	private final List<Agent> _agents = new ArrayList<Agent>();
	
	/** Rooms of the level by their ID. */
	private final Map<Integer, Room> _rooms = 
		new LinkedHashMap<Integer, Room>();
	
	/** Assorted positions in the map. */
	private final PositionHolder _positions = new PositionHolder();

	/** Items of the map by their ID. */
	private final Map<Integer, Item> _items = 
		new LinkedHashMap<Integer, Item>();
	
	
	/** Required number of traps to generate. */
	private int _requiredTrapRoomCount = 0;
	
	
	/** Notes to display at the beginning of the level. */
	private List<String> _levelNotes = new LinkedList<String>();
	
	
	// -------------------------------------------------------------------------
	// constructors:
	
	
	/**
	 * 
	 * 
	 * @param nextfreeID
	 */
	public DataMap(int nextFreeId, int requiredTrapRoomCount) {
		this._nextID  = nextFreeId;
		this._requiredTrapRoomCount = requiredTrapRoomCount;
	}
	
	
	/**
	 * Copy constructor.
	 * 
	 * @param other
	 */
	protected DataMap(DataMap other) {
		
		this._nextID = other._nextID;
		
		this._requiredTrapRoomCount = other._requiredTrapRoomCount;
		
		this._width = other._width;
		this._height = other._height;
		
		for(Room room : other._rooms.values()){
			this.addRoom(room.copy(this));
		}
		
		for(Position pos : other.getPositions()){
			this.addPosition(pos.copy(this));
		}
		
		this.connectPositions();
		
		for(Agent agent : other.getAgents()){
			this._agents.add(agent.copy(this));
		}
		
		this.addItems(other.getItems());
	}
	
	
	// -------------------------------------------------------------------------
	
	
	/**
	 * Adds new rooms to the game map.
	 * 
	 *  Also inserts empty floor positions if needed.
	 * 
	 *  @param objs
	 * */
	public final void addRooms(List<Room> objs) {
		for(Room obj : objs) {
			// insert the current room:
			this.addRoom(obj);	
		}
	}
	
	
	/**
	 * Adds new rooms to the game map.
	 * 
	 * Also inserts empty floor positions if needed.
	 *  
	 * @param room
	 */
	public final void addRoom(Room room) {
		// insert the room itself: 
		this._rooms.put(room.getId(), room);
		
		// insert empty floor positions:
		for(int x = room.getX(); x < room.getX() + room.getWidth(); x++){
			for(int y = room.getY(); y < room.getY() + room.getHeight(); y++){
				
				// control whether it already exists
				// if not, create it:
				Position position = this.getPosition(x, y);
				if(position == null){
					position = new Floor(this.getNextID(), x, y, room, this);
					this.addPosition(position);
				}
			}
		}
	}
	
	
	// -------------------------------------------------------------------------
	
	
	/** 
	 * Adds new positions to the game map.
	 * 
	 * @param objs
	 */
	public final void addPositions(List<Position> objs) {
		for(Position obj : objs){
			this.addPosition(obj);
		}
	}
	
	
	/** 
	 * Adds a new position to the game map.
	 * 
	 * It also adds the position to the room.
	 * 
	 * @param objs
	 */
	public final void addPosition(Position obj) {
		// control whether it already exists, and remove it:
		this.removePosition(obj.getX(), obj.getY());
				
		// insert the position:
		this._positions.addPosition(obj);
		
		// extend the dimensions of the whole map if needed:
		if(obj.getX() > this._width)
			this._width = obj.getX();
		if(obj.getY() > this._height)
			this._height = obj.getY();
		
		if(obj.isTypeOf(BaseInterface.Type.DOOR)){
			Room[] rooms = ((Door)obj).getRooms();
			rooms[0].addPosition(obj);
			rooms[1].addPosition(obj);
		}else{
			this.getRoom(obj.getRoomId()).addPosition(obj);
		}
		
	}
	
	
	/**
	 * Removes a position with the selected coordinates.
	 * 
	 * @param x horizontal
	 * @param y vertical
	 * @return success indicator
	 */
	protected final boolean removePosition(int x, int y) {
		return this._positions.removePosition(x, y);
	}
	
	
	/**
	 * Removes a position with the selected identifier.
	 * 
	 * @param id unique identifier
	 * @return success indicator
	 */
	protected final boolean removePosition(int id) {
		return this._positions.removePosition(id);
	}
	
	/** 
	 * Adds new agents to the game map.
	 * 
	 * @param objs list of agents
	 */
	public final void addAgents(List<Agent> objs) {
		for(Agent obj : objs) {
			// insert the agent: 
			this._agents.add(obj);
		}
	}
	
	
	/** 
	 * Adds new agent to the game map.
	 * 
	 * @param agent
	 */
	public final void addAgent(Agent agent) {
		this._agents.add(agent);
	}
	
	
	/** 
	 * Removes an agent from the game map.
	 * 
	 * @param agent
	 */
	public final void removeAgent(Agent agent) {
		this._agents.remove(agent);
	}
	
	
	/**
	 * Adds new items to the game map (only if an item with such an id does not yet exist).
	 * 
	 * @param objs list of game items
	 */
	public final void addItems(List<Item> objs) {
		for(Item obj : objs){
			if(this._items.containsKey(obj.getId()))
				continue;
			// insert the item: 
			this._items.put(obj.getId(), obj);
		}
	}
	
	
	/**
	 * Adds a new item to the game map (only if an item with such an id does not yet exist).
	 * 
	 * @param objs 
	 */
	public final void addItem(Item obj) {
		
		if(this._items.containsKey(obj.getId()))
			return;
		// insert the item: 
		this._items.put(obj.getId(), obj);
	}
	
	
	/**
	 * Adds the notes that should be displayed at the beginning of the level.
	 * 
	 * @param notes list of notes
	 */
	public final void addLevelNotes(List<String> notes) {
		this._levelNotes.addAll(notes);
	}
	
	
	// -------------------------------------------------------------------------
	// add traps:
	
	
	/** 
	 * Adds a camera object to the selected room.
	 * 
	 * @param roomId id of the room to add the camera.
	 */
	public final void addCameraToRoom(int roomId) {
		List<Position> floors = this._positions.getFloorPositions(roomId);
		Random generator = new Random();
		Position toRemove = floors.get(generator.nextInt(floors.size()));
		//this._positions.removePosition(toRemove);
		
		Camera camera = 
				new Camera(
						toRemove.getId(),
						toRemove.getX(),
						toRemove.getY(),
						roomId,
						true,
						this);
		
		this.addPosition(camera);
		
		for(int x = toRemove.getX() - 1; x <= toRemove.getX() + 1; x++){
			for(int y = toRemove.getY() - 1; y <= toRemove.getY() + 1; y++){
				Position pos = this.getPosition(x, y);
				if(pos != null && pos != camera){
					camera.connect((BasePosition)pos);
					pos.connect(camera);
				}
			}
		}
	}
	
	
	/**
	 * Sets how many traps has to be generated.
	 * 
	 * @param newRequiredCount
	 */
	public void setRequiredTrapRoomCount(int newRequiredCount) {
		this._requiredTrapRoomCount = newRequiredCount;
	}
	
	
	// -------------------------------------------------------------------------
	// getter methods:
	
	
	/**
	 * Returns a new, unused identifier.
	 * 
	 * @return a new, unused identifier
	 *  */
	public final int getNextID() {
		return this._nextID++;
	}
	
	
	/**
	 * Returns how many traps has to be generated.
	 * 
	 * @return how many traps has to be generated.
	 */
	@Override
	public int getRequiredTrapRoomCount() {
		return this._requiredTrapRoomCount;
	}
	
	
	/**
	 * Returns a list of all rooms in the map.
	 * 
	 * @return a copy of our room list.
	 */
	@Override
	public List<Room> getRooms() {
		List<Room> ret = new ArrayList<Room>(this._rooms.values().size());
		for(Room room : this._rooms.values()){
			ret.add(room);
		}
		return ret;
	}
	
	

	/**
	 * Returns the IDs of the rooms in the map.
	 * 
	 * @return list of identifiers.
	 */
	@Override
	public List<Integer> getRoomIds() {
		List<Integer> ret = new ArrayList<Integer>(this._rooms.keySet().size());
		for(Integer id : this._rooms.keySet()){
			ret.add(id);
		}
		return ret;
	}
	
	
	/**
	 * Decides whether two rooms are connected through doors.
	 * 
	 * @param roomIdA 
	 * @param roomIdB
	 * @return
	 */
	public boolean areNeighbouringRooms(int roomIdA, int roomIdB) {
		List<Position> rooms = this._positions.getDoors();
		for(Position pos : rooms){
			int[] currentRooms = ((Door)pos).getRoomIds();
			if(
				(currentRooms[0] == roomIdA && currentRooms[1] == roomIdB) ||
				(currentRooms[0] == roomIdB && currentRooms[1] == roomIdA)
			){
				return true;
			}
		}
		return false;
	}
	
	
	/**
	 * Creates a component list of the room IDs.
	 * 
	 * The rooms are considered as graph nodes and the doors are used as connections.
	 * 
	 * @return component lists
	 */
	public List<List<Integer>> breakToComponents(List<Integer> roomIds) {
		if(roomIds.isEmpty())
			return new LinkedList<List<Integer>>();
		
		// initialize component-list
		List<Integer> componentIds = new LinkedList<Integer>();
		for(int index = 0; index < roomIds.size(); index++){
			componentIds.add(0);
		}
		
		List<List<Integer>> result = new LinkedList<List<Integer>>();
		
		List<Integer> unused = new LinkedList<Integer>();
		for(Integer id : roomIds)
			unused.add(id);
		
		List<Integer> cue = new LinkedList<Integer>();
		List<Integer> sublist = null;
		List<Integer> toRemove = new LinkedList<Integer>();
		int current;
		while(unused.isEmpty() == false){
			if(cue.isEmpty()){
				current = unused.remove(0);
				cue.add(current);
				sublist = new LinkedList<Integer>();
				sublist.add(current);
				result.add(sublist);
			}
			current = cue.remove(0);
			for(int i = 0; i < unused.size(); i++){
				int currentUnused = unused.get(i);
				if(this.areNeighbouringRooms(current, currentUnused)){
					sublist.add(currentUnused);
					cue.add(currentUnused);
					toRemove.add(currentUnused);
				}
			}
			for(int i : toRemove){
				for(int index = 0; index < unused.size(); index++){
					if(unused.get(index) == i){
						unused.remove(index);
						break;
					}
				}
			}
			toRemove.clear();
		}
		
		return result;
	}
	
	
	/**
	 * Returns the room with the selected identifier.
	 * 
	 * @param id identifier
	 * @return room object or null.
	 */
	@Override
	public Room getRoom(int id) {
		return this._rooms.get(new Integer(id));
	}
	
	
	// -------------------------------------------------------------------------
	
	
	@Override
	public Position getPosition(int id) {
		return this._positions.getPosition(id);
	}
	
	
	@Override
	public Position getPosition(Node node) {
		return this._positions.getPosition(node);
	}
	
	
	@Override
	public Position getPosition(int x, int y) {
		return this._positions.getPosition(x, y);
	}
	
	
	@Override
	public List<Position> getPositions() {
		return this._positions.getPositions();
	}
	
	
	public List<Position> getFloorPositions(int roomId) {
		return this._positions.getFloorPositions(roomId);
	}
	
	
	public Position getActiveVender(int roomId) {
		return this._positions.getActiveVender(roomId);
	}
	
	
	@Override
	public List<Position> getOperablePositions() {
		return this._positions.getOperablePositions();
	}
	
	
	public List<Position> getTrapPositions() {
		return this._positions.getTrapPositions();
	}
	
	
	@Override
	public List<Room> getTrapRooms() {
		List<Room> trapRooms = new ArrayList<Room>();
		
		for(Position pos : this._positions.getTrapPositions()){
			if(
				((Camera)pos).isActive() &&
				trapRooms.contains(pos.getRoom()) == false
			)
				trapRooms.add(pos.getRoom());
		}
		
		for(Agent agent : this._agents){
			if(
				agent.isTypeOf(BaseInterface.Type.GUARD) &&
				agent.isInState(Agent.State.WELL)
			){
				Position pos = agent.getPosition();
				if(pos.isTypeOf(BaseInterface.Type.DOOR)){
					Room[] rooms = ((Door)pos).getRooms();
					if(trapRooms.contains(rooms[0]) == false)
						trapRooms.add(rooms[0]);
					if(trapRooms.contains(rooms[1]) == false)
						trapRooms.add(rooms[1]);
				}else{
					if(trapRooms.contains(agent.getRoom()) == false)
					trapRooms.add(agent.getRoom());
				}
			}
		}
		
		return trapRooms;
	}
	
	
	@Override
	public List<Integer> getTrapRoomIds() {
		List<Integer> trapRooms = new ArrayList<Integer>();
		int currentRoom = -1;
		
		for(Position pos : this._positions.getTrapPositions()){
			if(
				((Camera)pos).isActive() &&
				trapRooms.contains(pos.getRoomId()) == false
			)
				trapRooms.add(pos.getRoomId());
		}
		
		for(Agent agent : this._agents){
			if(
				agent.isTypeOf(BaseInterface.Type.GUARD) &&
				agent.isInState(Agent.State.WELL)
			){
				Position pos = agent.getPosition();
				if(pos.isTypeOf(BaseInterface.Type.DOOR)){
					int[] rooms = ((Door)pos).getRoomIds();
					if(trapRooms.contains(rooms[0]) == false)
						trapRooms.add(rooms[0]);
					if(trapRooms.contains(rooms[1]) == false)
						trapRooms.add(rooms[1]);
				}else{
					if(trapRooms.contains(agent.getRoomId()) == false)
						trapRooms.add(agent.getRoomId());
				}
			}
		}
		
		return trapRooms;
	}
	
	
	// -------------------------------------------------------------------------
	
	
	@Override
	public Item getItem(int id) {
		return this._items.get(new Integer(id));
	}
	
	
	@Override
	public List<Item> getItems() {
		List<Item> ret = new ArrayList<Item>(this._items.values().size());
		for(Item item : this._items.values()){
			ret.add(item);
		}
		return ret; 
	}
	
	
	// -------------------------------------------------------------------------
	
	
	@Override
	public List<Agent> getAgents() {
		return new ArrayList<Agent>(this._agents);
	}
	
	
	@Override
	public List<Agent> getPassiveAgents() {
		List result = new LinkedList<Agent>();
		for(Agent agent : this._agents){
			if(agent.isInState(Agent.State.STUNNED)){
				result.add(agent);
			}
		}
		return result;
	}
	
	
	@Override
	public Agent getAgent(int id) {
		for(Agent agent : this._agents)
			if(agent.getId() == id)
				return agent;
		return null;
	}
	
	
	@Override
	public Burglar getBurglar() {
		for(Agent agent : this._agents)
			if(agent.isTypeOf(BaseObject.Type.BURGLAR))
				return (Burglar)agent;
		return null;
	}
	
	
	@Override
	public List<Guard> getGuards() {
		List<Guard> guards = new ArrayList<Guard>(this._agents.size());
		for(Agent agent : this._agents)
			if(agent.isTypeOf(BaseObject.Type.GUARD))
				guards.add((Guard)agent);
		return guards;
	}
	
	
	// -------------------------------------------------------------------------
	
	
	@Override
	public List<String> getLevelNotes() {
		return this._levelNotes;
	}
	
	
	// -------------------------------------------------------------------------
	
	
	@Override
	public List<BaseObject> getObjectsOnPosition(int x, int y) {
		List<BaseObject> ret = new ArrayList<BaseObject>();
		
		Position pos = this.getPosition(x, y);
		if(pos == null)
			return ret;
		
		ret.add((BaseObject)pos);
		
		for(Agent agent : this._agents)
			if(agent.getPosition().getId() == pos.getId())
				ret.add((BaseObject)agent);
		
		return ret;
	}
	
	
	// -------------------------------------------------------------------------
	
	
	/** 
	 * Connects the neighboring positions.
	 * 
	 * A position is neighboring if it is above, below, 
	 * on the right or on the left.
	 */
	public final void connectPositions() {
		for(Position current : this._positions.getPositions()){
			for(int x = current.getX() - 1; x <= current.getX() + 1; x++){
				for(int y = current.getY() - 1; y <= current.getY() + 1; y++){
					Position neighbour = this._positions.getPosition(x, y);
					if(neighbour == null || neighbour == current)
						continue;
					current.connect((BasePosition)neighbour);
				}
			}
		}
	}
	
	
	// -------------------------------------------------------------------------
	
	
	@Override
	public Direction getDirection(Position from, Position to) {
		
		if(from.getX() < to.getX()){
			if(from.getY() < to.getY()){
				return Direction.SOUTH_EAST;
			}
			if(from.getY() == to.getY()){
				return Direction.EAST;
			}
			if(from.getY() > to.getY()){
				return Direction.NORTH_EAST;
			}
		}
			
		if(from.getX() == to.getX()){
			if(from.getY() < to.getY()){
				return Direction.SOUTH;
			}else{
				return Direction.NORTH;
			}
		}
			
		if(from.getX() > to.getX()){
			if(from.getY() < to.getY()){
				return Direction.SOUTH_WEST;
			}
			if(from.getY() == to.getY()){
				return Direction.WEST;
			}
			if(from.getY() > to.getY()){
				return Direction.NORTH_WEST;
			}
		}
		
		// will not happen;
		return Direction.WEST;
	}
	
	
	@Override
	public Position getNeighbour(Position position, Direction direction) {
		int x = position.getX();
		int y = position.getY();
		
		
		switch(direction){
			case SOUTH_EAST:
				return this.getPosition(x + 1, y + 1);
			case EAST:
				return this.getPosition(x + 1, y);
			case NORTH_EAST:
				return this.getPosition(x + 1, y - 1);
			case SOUTH:
				return this.getPosition(x, y + 1);
			case NORTH:
				return this.getPosition(x, y - 1);
			case SOUTH_WEST:
				return this.getPosition(x - 1, y + 1);
			case WEST:
				return this.getPosition(x - 1, y);
			case NORTH_WEST:
				return this.getPosition(x - 1, y - 1);
		}
		
		return null;
	}
	
	
	// -------------------------------------------------------------------------
	
	
	@Override
	public int getWidth() {
		return this._width;
	}
	
	
	@Override
	public int getHeight() {
		return this._height;
	}
	
	
	// -------------------------------------------------------------------------
	
	
	/**
	 * Helper class implementing the search functionality in the game positions.
	 */
	private class PositionHolder {
		
		
		/** The position objects. */
		private final List<Position> _positions = 
			new LinkedList<Position>();
		
		/** The position objects by identifier. */
		private final Map<Integer, Position> _byId = 
			new LinkedHashMap<Integer, Position>();
		
		/** The position objects by their A* node. */
		private final Map<Node, Position> _byNode = 
			new LinkedHashMap<Node, Position>();
		
		/** Lines of the layout by their vertical position. */
		private final Map<Integer, MapLine> _byY = 
			new LinkedHashMap<Integer, MapLine>();
		
		/** The position that are holding a camera. */
		private final List<Position> _trapPositions = new ArrayList<Position>();
		
		/** The position which can be operated by an agent or the player. */
		private final List<Position> _operablePositions = new ArrayList<Position>();
		
		
		// ---------------------------------------------------------------------
		
		
		/**
		 * Adds a single position to the layout.
		 * 
		 * @param position
		 */
		public void addPosition(Position position) {
			this._byId.put(position.getId(), position);
			
			this._byNode.put(((BasePosition)position).getNode(), position);
			
			this._positions.add(position);
			
			MapLine line = this._byY.get(position.getY());
			if(line == null){
				line = new MapLine();
				this._byY.put(position.getY(), line);
			}
			line.addPosition(position);
			
			// add to trap positions if needed:
			if(position.isTrap()){
				this._trapPositions.add(position);
			}
			
			// add to operable positions if needed:
			if(position.isOperable()){
				this._operablePositions.add(position);
			}
			
		}
		
		
		/**
		 * Removes a single position from all containers.
		 * 
		 * @param id position identifier
		 * @return success indicator
		 */
		public boolean removePosition(int id) {
			Position pos = this._byId.get(id);
			if(pos == null)
				return false;
			return this.removePosition(pos);
		}
		
		
		/**
		 * Removes a single position from all containers.
		 * 
		 * @param position  position object
		 * @return success indicator
		 */
		public boolean removePosition(Position position) {
			position.disconnect();
			boolean result = this._positions.remove(position);
			this._byId.remove(position.getId());
			this._byNode.remove(((BasePosition)position).getNode());
			
			MapLine line = this._byY.get(position.getY());
			if(line != null)
				line.removePosition(position.getX());
			
			if(position.isTrap())
				this._trapPositions.remove(position);
			
			if(position.isOperable())
				this._operablePositions.remove(position);
			
			return result;
		}
		
		
		/**
		 * Removes a single position from all containers.
		 * 
		 * @param x horizontal
		 * @param y vertical
		 * @return success indicator
		 */
		public boolean removePosition(int x, int y) {
			MapLine line = this._byY.get(y);
			if(line == null)
				return false;
			Position position = line.get(x);
			if(position == null)
				return false;
			
			return this.removePosition(position);
		}
		
		
		// ---------------------------------------------------------------------
		
		
		/**
		 * Returns a position object by identifier.
		 * 
		 * @param id
		 * @preturn position object or null
		 */
		public Position getPosition(int id) {
			return this._byId.get(id);
		}
		
		
		/**
		 * Returns a position object by A* node.
		 * 
		 * @param node
		 * @preturn position object or null
		 */
		public Position getPosition(Node node) {
			return this._byNode.get(node);
		}
		
		
		/**
		 * Returns the position on the selected coordinates.
		 * 
		 * @param x horizontal
		 * @param y vertical
		 * @return position object or null
		 */
		public Position getPosition(int x, int y) {
			MapLine line = this._byY.get(y);
			if(line == null)
				return null;			
			return line.get(x);
		}
		
		
		/**
		 * Returns a list copy of all positions.
		 * 
		 * @return a new list of positions.
		 */
		public List<Position> getPositions() {
			return new ArrayList<Position>(this._positions);
		}
		
		
		/**
		 * Returns a list copy of all floor positions in a room.
		 * 
		 * @param  roomId room identifier
		 * @return a new list of positions.
		 */
		public List<Position> getFloorPositions(int roomId) {
			List<Position> result = new LinkedList<Position>();
			for(Position pos : this._positions){
				if(pos.getRoomId() == roomId && pos.isTypeOf(BaseInterface.Type.FLOOR))
					result.add(pos);
			}
			return result;
		}
		
		
		/**
		 * Returns the first activated vending machine in a room.
		 * 
		 * @param  roomId room identifier
		 * @return a position or null
		 */
		public Position getActiveVender(int roomId) {
			for(Position pos : this._operablePositions){
				if(
					pos.getRoomId() == roomId &&
					pos.isTypeOf(BaseInterface.Type.VENDER) &&
					((Vender)pos).hasDropped()
				)
					return pos;
			}
			return null;
		}
		
		
		/**
		 * Returns all the doors in the layout in a new list.
		 * 
		 * @return all the doors on the map
		 */
		public List<Position> getDoors() {
			List<Position> result = new LinkedList<Position>(); 
			for(Position pos : this._operablePositions){
				if(pos.isTypeOf(BaseInterface.Type.DOOR))
					result.add(pos);
			}
			return result;
		}
		
		
		/**
		 * Returns all the interactive positions in the layout in a new list.
		 * 
		 * @return all the operable positions on the map
		 */
		public List<Position> getOperablePositions() {
			return new ArrayList<Position>(this._operablePositions);
		}
		
		
		/**
		 * Returns all the cameras in the layout in a new list.
		 * 
		 * @return all the cameras on the map
		 */
		public List<Position> getTrapPositions() {
			return new ArrayList<Position>(this._trapPositions);
		}
		
		
		// ---------------------------------------------------------------------
		
		
		/** Helper object representing a line. */
		private class MapLine {
			
			
			/** Positions on the line by horizontal coordinate. */
			private final Map<Integer, Position> _byX = 
				new LinkedHashMap<Integer, Position>();
			
			
			// -----------------------------------------------------------------
			
			
			/**  
			 * Adds a new position.
			 * 
			 * @param position
			 */
			public void addPosition(Position position) {
				this._byX.put(position.getX(), position);
			}
			
			
			/**  
			 * Removes a position by horizontal coordinate.
			 * @param x
			 * @return success indicator
			 */
			public Position removePosition(int x) {
				return this._byX.remove(x);
			}
			
			
			/**  
			 * Returns a position by horizontal coordinate.
			 * @param x
			 * @return position or null
			 */
			public Position get(int x) {
				return this._byX.get(x);
			}
			
		}
		
	}
	
}
